A conventional method of searching for digital images in a database containing images is based on a system of indexing images in the database.
The aim of an indexing system is to associate, with each image in the database, an information item characteristic of the content of the image referred to as the “image index”. The set of these information items constitutes what is designated by the “database index”. Typically, the content of an image is characterised by its colour distribution (histogram), its texture or its form.
A user interrogates a database of images through a query containing an information item characteristic of the image type sought. Conventionally, this query is constituted by an example image. The user chooses an image, from the database or external to it, whose content is similar to the image type sought. The content of the example image is then compared with the content of the database index according to a search strategy. Finally, the image in the database whose indexed information item has the greatest similarity to the content of the example image is extracted. Generally, a number of images are extracted from the database to be presented to the user, arranged according to the significance of their similarity with the query. The said user then makes a choice from amongst the images presented.
Conventionally, there are two approaches for defining the search strategy. It may be of the linear type or the hierarchical type.
The linear approach consists of considering the database as a single vector, each component of which is an image associated with an index. The strategy then consists of calculating the similarity between the index of the example image and that associated with each of the components of this vector. This strategy is easy to implement, which explains why it is often used. However, when the database contains a large number of images, of the order of several thousand, the calculation time for the search may be very long, which penalizes accordingly the time for responding to a query.
In order to reduce the above-mentioned calculation time, the hierarchical approach can be used. One known hierarchical search technique uses, for each image in the database, an index composed of two distinct parts which will be referred to here as “sub-indices”. Amongst these two sub-indices, a first sub-index is of a not very discriminant type, while the second sub-index is of a more discriminant type.
The search process then takes place in two steps. During a first step referred to as a “filtering step”, a “coarse” sorting of the images in the database is carried out using the first sub-indices. At the end of this step, a subset of images is selected. A second step, referred to as a “matching step” is then carried out, this time performed on the subset of images retained during the first step, during which the search is refined using the second sub-indices. At the end of this second step, only the images most resembling the example image are kept.
An example of a hierarchical search method is given in the article entitled “Multiresolution video indexing for subband video database”, by J. Lee and B. W. Dickinson, Proc. of SPIE: Storage and retrieval for images and videos databases, vol. 2185, San Jose, Calif., February 1994. The search method taught in this article applies to images compressed by a subband decomposition technique. Each of the subbands of an image has an index associated with it. According to this search method, a start is made by comparing the indices associated with the so-called “low frequency” band of the images, then the search result obtained is refined by a comparison of the indices associated with the higher frequency bands.
Generally speaking, the known hierarchical search methods of the prior art use indices which characterise the overall content of the images. Thus, in the search method taught in the above-mentioned document, the indices characterise the overall content of the image according to a number of levels of resolution. However, in these search methods, the index of a given image never characterises the visual content of this image according to its spatial distribution over the whole image medium. The taking into account of the spatial distribution of the content by the image index would nevertheless make it possible to increase the accuracy of this index and therefore the accuracy of the search using such an index.